class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode cur1 = l1, cur2 = l2; // 初始化两个指针分别指向两个链表的头节点
        ListNode newHead = new ListNode(0); // 创建一个虚拟头结点，方便记录结果
        ListNode prev = newHead; // 尾插操作的尾指针
        int t = 0; // 记录进位

        // 遍历两个链表，直到两个链表都为空且没有剩余的进位
        while (cur1 != null || cur2 != null || t != 0) {
            // 如果第一个链表的当前节点不为空，将它的值加到 t 中，并移动指针
            if (cur1 != null) {
                t += cur1.val;
                cur1 = cur1.next;
            }
            // 如果第二个链表的当前节点不为空，将它的值加到 t 中，并移动指针
            if (cur2 != null) {
                t += cur2.val;
                cur2 = cur2.next;
            }
            // 创建新节点，存储当前位的值（t % 10），并将其链接到结果链表
            prev.next = new ListNode(t % 10);
            prev = prev.next; // 移动尾指针
            // 更新进位
            t /= 10;
        }
        // 返回结果链表的头节点（虚拟头节点的下一个节点）
        return newHead.next;
    }

    public static void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        // 创建第一个链表：2 -> 4 -> 3
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(3);

        // 创建第二个链表：5 -> 6 -> 4
        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);

        Solution solution = new Solution();
        ListNode result = solution.addTwoNumbers(l1, l2);

        printList(result); // 应该输出：7 -> 0 -> 8 -> null
    }
}